package dataStructure;


import java.util.*;

public class Graph {
    /**
     * 邻接矩阵存储方式
     */
    static class MGraph {
        ArrayList<Character> Vex;
        int[][] Edge;
        int vexnum, arcnum;

        public MGraph() {
            Scanner scanner = new Scanner(System.in);
            ArrayList<Character> vex = new ArrayList<>();
//            ABCDEF
//            System.out.println("输入顶点表无需间隔");
//            String line = scanner.nextLine();
            //测试数据
            String line = "ABCDEFGH";

            char[] chars = line.toCharArray();
            for (char aChar : chars) {
                vex.add(aChar);
            }
            int size = vex.size();
//            0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0
//            System.out.println("输入边表空格间隔");
            int[][] de = new int[size][size];
            //测试数据
            int[] data = new int[]{0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0};
            int z = 0;

            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    de[i][j] = data[z];
                    z++;
                }
            }
            int k = 0;
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (de[i][j] == 1) {
                        k++;
                    }

                }
            }
            k = k / 2;
            this.Vex = vex;
            this.Edge = de;
            this.vexnum = size;
            this.arcnum = k;
        }

        /**
         * 判断是否有边x,y
         *
         * @param G
         * @param x
         * @param y
         */
        public void Adjacent(MGraph G, Character x, Character y) {
            int indexX = G.Vex.indexOf(x);
            int indexY = G.Vex.indexOf(y);
            System.out.println(G.Edge[indexX][indexY] == 1 ? "true" : "false");
        }

        /**
         * 列出x相邻的边
         *
         * @param G
         * @param x
         * @param isdirected 是否为有向图,true有向,false无向
         */
        public ArrayList<Character> Neighbors(MGraph G, Character x, Boolean isdirected) {
            if (!isdirected) {
                //无向图
                int indexX = G.Vex.indexOf(x);
                ArrayList<Character> list = new ArrayList<>();
                for (int i = 0; i < vexnum; i++) {
                    if (G.Edge[indexX][i] == 1) {
                        list.add(G.Vex.get(i));
                    }
                }
                return list;
            } else {
                //有向图
                int indexX = G.Vex.indexOf(x);
                ArrayList<Character> list = new ArrayList<>();
                for (int i = 0; i < vexnum; i++) {
                    if (G.Edge[indexX][i] == 1) {
                        list.add(G.Vex.get(i));
                    }
                }
                list.add('/');
                for (int i = 0; i < vexnum; i++) {
                    if (G.Edge[i][indexX] == 1) {
                        list.add(G.Vex.get(i));
                    }
                }
                return list;
            }

        }

        /**
         * 广度优先
         */
        public void BFSTraverse(MGraph G, int v) {
            Boolean[] visited = new Boolean[G.vexnum];
            Arrays.fill(visited, false);
            BFS(G, v, visited);
            for (int i = 0; i < visited.length; i++) {
                if (!visited[i]) {
                    System.out.println("非联通图");
                    BFS(G, i, visited);
                }
            }
        }

        public static void BFS(MGraph G, int v, Boolean[] visited) {
            Arrays.fill(visited, false);
            Queue<Integer> queue = new LinkedList<>();
            System.out.println(G.Vex.get(v));
            visited[v] = true;
            queue.add(v);
            while (!queue.isEmpty()) {
                Integer remove = queue.remove();
                ArrayList<Character> list = G.Neighbors(G, G.Vex.get(remove), false);

                for (Character i :
                        list) {
                    int index = G.Vex.indexOf(i);
                    if (!visited[index]) {
                        System.out.println(G.Vex.get(index));
                        visited[index] = true;
                        queue.add(index);
                    }
                }

            }
        }

    }

    /**
     * 邻接表法
     */
    //边表结点
    static class ArcNode {
        int adjust;
        //下一条弧
        ArcNode next;

        public void setNext(ArcNode next) {
            this.next = next;
        }

        public ArcNode(int adjust) {
            this.adjust = adjust;
            this.next = null;
        }
    }

    //顶点表信息
    static class VNode {
        Character data;
        //第一条弧
        ArcNode first;

        public VNode(Character data, ArcNode first) {
            this.data = data;
            this.first = first;
        }

        public ArcNode selectLastNode(ArcNode node) {
            if (node.next != null) {
                return selectLastNode(node.next);
            } else {
                return node;
            }
        }
    }

    //邻接表
    static class ALGraph {
        ArrayList<VNode> vertices;
        int vexnum, arcnum;

        /**
         * 获取x的序号
         */
        public int indexOf(Character x) {
            for (int i = 0; i < vertices.size(); i++) {
                if (vertices.get(i).data == x) {
                    return i;
                }
            }
            return -1;
        }

        public ALGraph() {
            String line = "ABCDE";
            char[] chars = line.toCharArray();
            ArrayList<int[]> nodeList = new ArrayList<int[]>() {{
                //有向图
//                add(new int[]{4});
//                add(new int[]{0});
//                add(new int[]{5});
//                add(new int[]{2,6});
//                add(new int[]{});
//                add(new int[]{1});
//                add(new int[]{2,5, 7});
//                add(new int[]{3});
                //无向图
                add(new int[]{1});
                add(new int[]{3});
                add(new int[]{3, 4});
                add(new int[]{4});
                add(new int[]{});
            }};
            ArrayList<VNode> list = new ArrayList<VNode>();

            for (int i = 0; i < chars.length; i++) {
                int[] ints = nodeList.get(i);
                VNode vNode = new VNode(chars[i], null);
                if (ints.length == 0) {
                } else {
                    vNode = new VNode(chars[i], new ArcNode(ints[0]));
                    for (int j = 1; j < ints.length; j++) {
                        vNode.selectLastNode(vNode.first).next = new ArcNode(ints[j]);
                    }
                }

                list.add(vNode);
            }

            this.vertices = list;
            this.vexnum = chars.length;
            this.arcnum = 1;
        }

        /**
         * 判断是否有边x,y
         */
        public Boolean Adjacent(ALGraph G, Character x, Character y) {
            int indexX = G.indexOf(x);
            int indexY = G.indexOf(y);
            ArcNode node = G.vertices.get(indexX).first;
            while (true) {
                if (node.adjust == indexY) {
                    return true;
                } else if (node.next == null) {
                    return false;
                }
                node = node.next;
            }
        }

        /**
         * x相邻的边
         *
         * @param G
         * @param x
         * @param isdirected
         * @return
         */
        public ArrayList<Character> Neighbors(ALGraph G, Character x, Boolean isdirected) {
            if (!isdirected) {
                ArcNode node = G.vertices.get(G.indexOf(x)).first;
                ArrayList<Character> list = new ArrayList<>();
                while (true) {
                    list.add(G.vertices.get(node.adjust).data);
                    if (node.next == null) {
                        return list;
                    } else {
                        node = node.next;
                    }
                }
            } else {
                ArrayList<Character> list = new ArrayList<>();
                //求入度
                /**
                 * 进行BFS时注释入度
                 */
//                for (int i = 0; i < G.vertices.size(); i++) {
//                    VNode node = G.vertices.get(i);
//                    ArcNode first = node.first;
//                    while (first!=null) {
//                        if (first.adjust == G.indexOf(x)) {
//                            list.add(G.vertices.get(i).data);
//                            break;
//                        } else if (first.next == null) {
//                            break;
//                        } else {
//                            first = first.next;
//                        }
//                    }
//                }
                //求出度
                VNode node = G.vertices.get(G.indexOf(x));
                ArcNode first = node.first;
                while (first != null) {
                    list.add(G.vertices.get(first.adjust).data);
                    if (first.next == null) {
                        break;
                    } else {
                        first = first.next;
                    }
                }
                return list;
            }
        }

        /**
         * 广度优先
         */
        public void BFSTraverse(ALGraph G, int v) {
            Boolean[] visited = new Boolean[G.vexnum];
            Arrays.fill(visited, false);
            BFS(G, v, visited);
            for (int i = 0; i < visited.length; i++) {
                if (!visited[i]) {
                    System.out.println("非联通图");
                    BFS(G, i, visited);
                }
            }
        }

        public void BFS(ALGraph G, int v, Boolean[] visited) {
            Queue<Integer> queue = new LinkedList<>();
            System.out.println(G.vertices.get(v).data);
            visited[v] = true;
            queue.add(v);
            while (!queue.isEmpty()) {
                Integer remove = queue.remove();
                /**
                 * 若邻接表有向图,编译求入度部分
                 */
                ArrayList<Character> list = G.Neighbors(G, G.vertices.get(remove).data, true);
//                System.out.println("list"+list);
                for (Character i :
                        list) {
                    int index = G.indexOf(i);

                    if (!visited[index]) {
                        System.out.println(G.vertices.get(index).data);
                        visited[index] = true;
                        queue.add(index);
                    }
                }

            }

        }

        public void DFSTraverse(ALGraph G, int v) {
            Boolean[] visited = new Boolean[G.vexnum];
            Arrays.fill(visited, false);
            DFS(G, v, visited);
            for (int i = 0; i < visited.length; i++) {
                if (!visited[i]) {
                    System.out.println("非联通图");
                    DFS(G, i, visited);
                }
            }
        }

        public void DFS(ALGraph G, int v, Boolean[] visited) {

//            System.out.println(G.vertices.get(v).data);
            visited[v] = true;
            ArrayList<Character> list = G.Neighbors(G, G.vertices.get(v).data, true);
            for (Character i :
                    list) {
                int index = G.indexOf(i);

                if (!visited[index]) {
                    DFS(G, index, visited);
                }
            }
            /*逆拓扑排序
                         */
            System.out.println(G.vertices.get(v).data);
//            for (int i = 0; i < visited.length; i++) {
//                if (!visited[i]) {
//                    System.out.println("从第" + i+"号开始遍历");
//                    DFS(G, i,visited);
//                }
//            }
        }

        public Boolean TopologicalSort(ALGraph G) {
            stack<Integer> S = new stack<>();
            int[] indegree = indegree(G);
            int[] print = new int[G.vertices.size()];
            for (int i = 0; i < G.vertices.size(); i++) {
                if (indegree[i] == 0) {
                    S.Push(i);
                }
            }
            int count = 0;
            while (!S.StackEmpty()) {
                Integer i = S.Pop();
                print[count++] = i;
                for (ArcNode p = G.vertices.get(i).first; p != null; p = p.next) {
                    int v = p.adjust;
                    indegree[v]--;
                    if (indegree[v] == 0) {
                        S.Push(v);
                    }
                }
            }
            if (count<G.vertices.size()){

                return false;
            }else {
                System.out.println(Arrays.toString(print));
                return true;
            }

        }

        /**
         * 计算第n号的入度
         *
         * @param n
         * @return
         */
        public int[] indegree(ALGraph G) {
            int[] inde = new int[100];
            Arrays.fill(inde, 0);
            for (int i = 0; i < G.vertices.size(); i++) {
                ArcNode node = G.vertices.get(i).first;
                while (node != null) {
                    inde[node.adjust]++;
                    if (node.next == null) {
                        break;
                    } else {
                        node = node.next;
                    }
                }
            }
            int[] result = Arrays.copyOf(inde, G.vertices.size());
            return result;
        }
    }


    public static void main(String[] args) {
//        MGraph graph = new MGraph();
//        System.out.println(graph.Neighbors(graph,'C',true));

//        ALGraph alGraph = new ALGraph();
//        System.out.println(alGraph.Neighbors(alGraph, 'C', true));


//        MGraph graph = new MGraph();
//        MGraph.BFS(graph,0);

        ALGraph alGraph = new ALGraph();
//        System.out.println(alGraph.Neighbors(alGraph,'D',true));
        alGraph.DFSTraverse(alGraph,1);

//        ALGraph alGraph = new ALGraph();
////        System.out.println(alGraph.Neighbors(alGraph,'D',true));
//        alGraph.TopologicalSort(alGraph);

    }


}
